Design engineers design IC's by transforming logical or circuit descriptions of IC's into geometric descriptions, called layouts. IC layouts typically include circuit modules with pins, and interconnect lines that connect the circuit-module pins. A net is typically defined as a collection of pins that need to be connected. A list of all or some of the nets in a layout is referred to as a net list.
To create layouts, design engineers typically use electronic design automation (“EDA”) applications. These applications provide sets of computer-based tools for creating, editing, and analyzing IC design layouts. Routers are one type of EDA tool. A router defines routes for interconnect lines that connect the pins of nets.
A router typically receives a routing problem that requires it to identify a route for each net in a net list. Some routers solve such a routing problem by first identifying multiple routes for each net. These routers then try to select a combination of routes that includes one route for each net and that optimizes a particular objective function. The objective function typically expresses one or more metric costs, such as length of routes, congestion in the design, etc.
Routers of this sort use different techniques to select the combination of routes from the set of identified solutions. One technique is randomized rounding. Generally, this technique is a probabilistic method that converts an exact solution of a relaxed problem into an approximate solution to an original problem. With randomized rounding, an EDA router interprets fractional routing solutions (e.g., solutions provided by a linear program) as probabilities for rounding the solutions. Numerous examples of this technique can be found in the literature. One such reference is disclosed in Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press (1995, 1997).
Randomized rounding works well in certain situations but not in others. For instance, one type of routing is global routing. Global routing typically identifies routes between cells, which partition the layout into several regions. Such cells are called Gcells. In global routing, randomized rounding works well when the Gcells are large, but does not work as well when the Gcells are small. Therefore, there is a need in the art for a better method for selecting a combination of routes from a set of routes that includes one or more routes for each net in a net list. More generally, there is a need for a better method for solving optimization problems.